#include <unordered_map>
#include <vector>
#include <algorithm>

using namespace std;


class Solution {
public:
	unordered_map<int, int> mm;
	vector<vector<int>> ans;
	vector<vector<int>> threeSum(vector<int>& nums) {
		sort(nums.begin(), nums.end());

		for (auto& e : nums) { mm[e]++; }

		int prevI = 100000 + 10;
		int prevJ = 100000 + 10;

		for (int i = 0; i < nums.size(); i++) {
			if (nums[i] == prevI) continue;
			mm[nums[i]]--;
			for (int j = i + 1; j < nums.size(); j++) {
				if (nums[j] == prevJ) continue;
				mm[nums[j]]--;
				int find = 0 - nums[i] - nums[j];
				if (find >= nums[i] && find >= nums[j]) {
					if (mm[find] > 0) {
						ans.push_back(vector<int>{nums[i], nums[j], find});
					}
				}
				mm[nums[j]]++;
				prevJ = nums[j];
			}
			mm[nums[i]]++;
			prevI = nums[i];
		}
		return ans;
	}
};

//int main() {
//
//
//	return 0;
//}